package leetcode.editor.cn;
import java.util.*;
//给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 
//
// 说明： 
//
// 
// 拆分时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
// 
//
// 示例 2： 
//
// 输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
//     注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
// 
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 👍 1174 👎 0

public class 单词拆分{
	public static void main(String[] args) {
		Solution solution = new 单词拆分().new Solution();
	    
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /*public boolean wordBreak(String s, List<String> wordDict) {
		boolean[] dp = new boolean[s.length() + 1];
		dp[0] = true;
		for (int i = 1; i <= s.length(); i++) {
			for (int j = 0; j < i; j++) {
				if(dp[j] && wordDict.contains(s.substring(j, i))){
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
	}*/
	public boolean wordBreak(String s, List<String> wordDict) {
		Trie trie = new Trie();
		trie.insert(s);
		boolean flag = true;
		while (flag){
			flag = false;
			for (String s1 : wordDict) {
				Trie node = trie.searchPrefix(s1);
				if(node!=null){
					trie = node;
					if(trie.isEnd){
						return true;
					}
					flag = true;
					break;
				}
			}
		}
		return false;
	}

	class Trie {
		private Trie[] children;
		private boolean isEnd;
		/** Initialize your data structure here. */
		public Trie() {
			children = new Trie[26];
			isEnd = false;
		}

		/** Inserts a word into the trie. */
		public void insert(String word) {
			Trie node = this;
			for (int i = 0; i < word.length(); i++) {
				char c = word.charAt(i);
				int index = (int) (c - 'a');
				if(node.children[index] == null){
					node.children[index] = new Trie();
				}
				node = node.children[index];
			}
			node.isEnd = true;
		}

		/** Returns if the word is in the trie. */
		public boolean search(String word) {
			Trie node = searchPrefix(word);
			return node!=null && node.isEnd;
		}

		/** Returns if there is any word in the trie that starts with the given prefix. */
		public boolean startsWith(String prefix) {
			Trie node = searchPrefix(prefix);
			return node!=null;
		}

		public Trie searchPrefix(String prefix) {
			Trie node = this;
			for (int i = 0; i < prefix.length(); i++) {
				char ch = prefix.charAt(i);
				int index = ch - 'a';
				if (node.children[index] == null) {
					return null;
				}
				node = node.children[index];
			}
			return node;
		}

	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
